/* 
 * $Id: OptExplicit.java 1259 2007-01-09 14:23:47Z tcoupaye $
 *
 * Behavior Protocols extensions for static and runtime checking
 * developed for the Julia implementation of Fractal.
 *
 * Copyright 2004
 *    Distributed Systems Research Group
 *    Department of Software Engineering
 *    Faculty of Mathematics and Physics
 *    Charles University, Prague
 *
 * Copyright (C) 2006
 *    Formal Methods In Software Engineering Group
 *    Institute of Computer Science
 *    Academy of Sciences of the Czech Republic
 *
 * Copyright (C) 2006 France Telecom
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 *
 * Contact: ft@nenya.ms.mff.cuni.cz
 * Authors: Jan Kofron <kofron@nenya.ms.mff.cuni.cz>
 */

package org.objectweb.fractal.bpc.checker.optimizer;


import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

import org.objectweb.fractal.bpc.checker.DFSR.CheckingException;
import org.objectweb.fractal.bpc.checker.DFSR.Options;
import org.objectweb.fractal.bpc.checker.node.*;
import org.objectweb.fractal.bpc.checker.state.Signature;
import org.objectweb.fractal.bpc.checker.state.State;
import org.objectweb.fractal.bpc.checker.state.TransitionPair;

/**
 * This class is used for building the explicit automata. The class constructor
 * is intended to obtain the top most treenode and to traverse the parse tree
 * and built the explicit automata in suitable situations. The construction of
 * the explicit automaton is done in similiar way as if the state space is
 * traversed while checking the compliance.
 */
public class OptExplicit {

    /** Creates a new instance of ExplicitAutomaton */
    public OptExplicit(TreeNode node, int threshold) {
        this.node = node;
        this.threshold = threshold;
    }

    /**
     * Performs the DFS traversing and builds the explicit automata
     * 
     * @return the topmost treenode
     */
    public TreeNode perform() throws InvalidParameterException {

        Stack shouldbuild = new Stack(); // indicates whether an explicit
        // automaton here would improve the performance
        boolean buildflag = false;
        Stack stack = new Stack();
        int memoryleft = Options.totalmemory - Options.statememory;
        memoryleft *= 3000;
        
        // this is a simple heuristic - each state has an
        // average size of Signature.getSize() bytes
        // and 2 transitions which results in the size of (3 * size) bytes per state, so
        // there can be for about 300 / size states within 1kB and 300 000 / size states automaton
        // within 1MB.

        stack.push(node);
        shouldbuild.push(new Boolean(buildflag));

        while (stack.size() > 0) {
            TreeNode actual = (TreeNode) stack.pop();
            buildflag = ((Boolean) shouldbuild.pop()).booleanValue();

            TreeNode[] children = actual.getChildren();

            if ((actual instanceof AndParallelNode) || (actual instanceof AdjustmentNode) || (actual instanceof CompositionNode))
                buildflag = true;

            for (int i = 0; i < children.length; ++i) {
                long weight = children[i].getWeight();
                if ((weight < threshold) && (buildflag)) {
                    children[i] = buildExplicit(children[i]);
                    memoryleft -= weight;
                    threshold = memoryleft < threshold ? memoryleft : threshold;
                } else {
                    stack.push(children[i]);
                    shouldbuild.push(new Boolean(buildflag));
                }

            }
        }

        // adjust the memory available for the state cache
        Options.statememory += (Signature.getSize() * memoryleft / 300000);

        return node;
    }

    /**
     * Builds an explicit automaton from given subtree
     * 
     * @param node
     *            the subtree sources for the explicit automaton
     * @return the explicit automaton
     */
    private TreeNode buildExplicit(TreeNode node) throws InvalidParameterException {
        TreeMap restrans = new TreeMap();
        State resinit;
        TreeSet resaccept = new TreeSet();
        TreeSet visited = new TreeSet();

        Stack stack = new Stack();

        State actual = node.getInitial();
        //actual.getSignature();

        resinit = actual;
        if (node.isAccepting(actual))
            resaccept.add(actual);

        stack.push(actual);

        while (stack.size() > 0) {
            actual = (State) stack.pop();
            actual.getSignature();

            if (!visited.contains(actual)) {

                if (node.isAccepting(actual))
                    resaccept.add(actual);

                TransitionPair[] trans;
                try {
                    trans = (TransitionPair[]) node.getTransitions(actual).transitions;
                }
                // only consent could generate this exception, but it shouldn't
                // be optimized in this way
                catch (CheckingException e) {
                    throw new RuntimeException("Internal checker error");
                }

                restrans.put(actual, trans);

                for (int i = 0; i < trans.length; ++i) {
                    stack.push(trans[i].state);
                }

                visited.add(actual);
            }
        }

        return new ExplicitNode(resinit, restrans, resaccept, node.protocol, node);
    }

    //----------------------------------------------------------------
    /**
     * The top most treenode
     */
    private TreeNode node;

    /**
     * The treshold indicates how big automama should be conversed to explicit
     * automata
     */
    private int threshold;

}
